\section{Architectural Design}


\begin{figure}
\begin{center}
\includegraphics[height=8in]{arch.pdf}
\end{center}
\caption{DiGr compiler block diagram\label{blockdiagram}}
\end{figure}

The DiGr compiler pipeline consists of five major modules along with a
final execution stage, and three backend/abstract syntax tree
definitions and libraries. A block diagram of the flow of information
and dependencies is pictured in Figure \ref{blockdiagram}.

\subsection{DiGr Compiler Modules}

The {\bf scanner} processes a stream of DiGr code and returns
tokens. If the input is not lexically correct DiGr code, the scanner
fails. At this stage, only the presence of unrecognizable tokens will
stop compilation.

The {\bf parser} then uses the grammar defined in the {\bf DiGr AST
  Definition} to turn the token sequence into an instance of the DiGr
AST. The AST is a recursive, typed OCaml tree of tuples. If the token
stream is not a syntactically correct DiGr program, compilation fails
at the parser stage.

The {\bf interpreter} performs static semantic type checking, scoping
and other consistency checks on the DiGr AST. If the AST does not
represent a semantically sensible DiGr program, compilation fails at
the interpreter stage. Unlike the first two modules, the interpreter
does not modify its input (the DiGr AST), but simply accepts or
rejects it. The interpreter generates symbol tables for the global and
all local scopes, but these do not remain after the interpreter stage.

The {\bf translator} turns the DiGr AST into an instance of the AST
described in the {\bf C++ AST Definition}. Much of the translation,
especially for the C++-like elements of the language, occurs in a
recursive, depth-first manner and is straightforward. The higher-level
elements of the DiGr are turned into significantly longer or more
complicated sequences of C++ statements. The translator does no
further semantic checking of its own, and this module always generates
a valid instance of a C++ abstract syntax tree. This is because any
problems encountered by the translator reflect either an incomplete or
inconsistent DiGr AST definition, or a failure of the interpreter to
properly validate the DiGr AST.

In terms of the block diagram, one could argue that the interpreter
and translator stages could be combined, since the interpreter does
not modify its input. However, we felt that separating the semantic
type checking (which can be thought of as part of the compiler
front-end) from the beginning of the compilation back-end was a good
abstraction. This way, development could be focused on either module,
since they perform non-overlapping tasks.

The {\bf compiler} recursively walks the C++ AST and outputs a C++
program. In effect, the compiler takes the semantic meaning of the C++
AST and turns it into a compilable program will all syntactic details
included. The compiler is blind to the semantic correctness (or
incorrectness) of the actual resulting program.

The sixth stage before program execution is compiling with {\bf g++}
against the {\bf DiGr C++ Backend} and running the resulting binary
program, but this is not a formal DiGr module. The C++ AST is
constrained so as to generate only syntactically valid C++, and the
interpreter and translator ensure that the output is {\em
  semantically} correct and will compile. Our test examples have been
checked against g++ version 4.4.3, but it is likely that any ISO
compliant C++ compiler will compile the DiGr output.

Unfortunately, there are errors it is impossible to check at compile
time, and difficult to handle gracefully at runtime. These include
segmentation faults from out of bounds accesses of C++ arrays and are
an unfortunate consequences of the


\subsection{Definitions and Libraries}

Several stages of the compiler use the {\bf DiGr AST Definition},
which represents a DiGr program with all syntactic details stripped
away. The AST definition was designed to split the difference between
being in a form easily constructed by the parser, and easily
interpreted and translated later.

The {\bf C++ AST Definition} implements the small but flexible subset
of the C++ language needed to output compiled DiGr code. The
definition takes some shortcuts (for example, there is no support for
shifting ({\tt >>}, {\tt <<}) operators or streams with the single
exception of using {\tt std::cout <<} to implement the DiGr {\tt
  print()} opt), and is meant to be lightweight to make compilation
easy. The C++ AST definition has no concept of semantic correctness.

Finally, the {\bf DiGr C++ Backend} is the engine against which
compiled DiGr C++ code can be turned into a binary executable. The
backend was written to have a simple interface to make the compilation
step efficient and clean, and also be short enough so that the
overhead in a DiGr binary program is relatively small. The backend
does a small amount of runtime error catching.
